#include "stdio.h"
typedef datatype char;
typedef struct bitnode
{
    datatype data;
    Struct bitnode *lchild, *rchild;
    //左右孩子指针
} BiTNode, *BiTree;
typedef struct BiThrNode
{
    datatype data;
    struct BiThrNode *lchild;
    struct BiThrNode *rchild;
    unsigned ltag;
    unsigned rtag;
} BiThrNodeType, *BiThrTree;
#pragma region 【算法 4 - 1(a)】建立一棵空的带头结点的二叉树
BiTree InitiateA() //初始建立一棵带头结点的二叉树
{
    BiTNode *bt;
    bt = (BiTNode *)malloc(sizeof(BiTNode));
    bt->lchild = NULL;
    bt->rchild = NULL;
    return bt;
}

//若要建立不带头结点的二叉树，可描述如下：
//【算法 4 - 1(b)】建立一棵空的不带头结点的二叉树
BiTree initiateB() //初始建立一棵不带头结点的二叉树
{
    BiTNode *bt;
    bt = NULL;
    return bt;
}
#pragma endregion
#pragma region 【算法 4 - 2】生成一棵以x 为根结点的数据域值以lbt 和rbt 为左右子树的二叉树
BiTree Create(elemtype x, BiTree lbt, BiTree rbt)
{
    BiTree p;
    if ((p = (BiTNode *)malloc(sizeof(BiTNode))) == NULL)
        return NULL;
    p->data = x;
    p->lchild = lbt;
    p->rchild = rbt;
    return p;
}
#pragma endregion
#pragma region 【算法4 - 3】在二叉树bt 中的parent 所指结点和其左子树之间插入数据元素为x 的结点
BiTree InsertL(BiTree bt，elemtype x，BiTree parent)
{
    BiTree p;
    if (parent == NULL)
    {
        printf("\n插入出错") ； return NULL;
    }
    if ((p = (BiTNode *)malloc(sizeof(BiTNode))) == NULL)
        return NULL;
    p->data = x;
    p->lchild = NULL;
    p->rchild = NULL;
    if (parent->lchild == NULL)
        parent->lchild = p;
    else
    {
        p->lchild = parent->lchild;
        parent->lchild = p;
    }
    return bt;
}
#pragma endregion
#pragma region 【算法 4 - 4】在二叉树bt 中删除parent 的左子树
BiTree DeleteL(BiTree bt，BiTree parent)
{
    BiTree p;
    if (parent == NULL || parent->lchild == NULL)
    {
        printf("\n删除出错") ； return NULL;
    }
    p = parent->lchild;
    parent->lchild = NULL;
    free(p);
    //当*p为非叶子结点时，这样删除仅释放了所删子树根结点的空间，
    //若要删除子树分支中的结点，需用后面介绍的遍历操作来实现。
    return bt;
}
#pragma endregion
#pragma region 【算法 4 - 5】先序遍历二叉树的递归算法
void PreOrder(BiTree bt)
{
    if (bt == NULL)
        return;           //递归调用的结束条件
    Visit(bt);            //访问根结点
    PreOrder(bt->lchild); //先序递归遍历bt的左子树
    PreOrder(bt->rchild); //先序递归遍历bt的右子树
}
#pragma endregion
#pragma region 【算法 4 - 6】中序遍历二叉树的递归算法
void InOrder(BiTree bt)
{
    if (bt == NULL)
        return;          //递归调用的结束条件
    InOrder(bt->lchild); //中序递归遍历bt的左子树
    Visit(bt);           //访问根结点
    InOrder(bt->rchild); //中序递归遍历bt的右子树
}
#pragma endregion
#pragma region 【算法 4 - 7】后序遍历二叉树的递归算法
void PostOrder(BiTree bt)
{
    if (bt == NULL)
        return;            //递归调用的结束条件
    PostOrder(bt->lchild); //后序递归遍历bt的左子树
    PostOrder(bt->rchild); //后序递归遍历bt的右子树
    Visite(bt);            //访问根结点
}
#pragma endregion
#pragma region 【算法 4 - 8】先序遍历的非递归算法
void NRPreOrder(BiTree bt)
{                               //非递归先序遍历二叉树
    BiTNode *stack[MAXNODE], p; //设足够大的栈空间
    int top = -1;               //栈初始化为空
    if (bt == NULL)
        return;
    p = bt;                           // p指向根结点
    while (!(p == NULL && top == -1)) //指针p为空且栈空时结束
    {
        while (p != NULL)
        {
            Visit(p); //访问当前结点
            top++;
            stack[top] = p; //将当前指针p压栈
            p = p->lchild； //指针指向p的左孩子结点
        }
        if (top < 0)
            return; //栈空时结束
        else
        {
            p = stack[top];
            top - -;       //从栈中弹出栈顶元素
            p = p->rchild; //到栈顶元素右子树
        }
    }
}
#pragma endregion
#pragma region 【算法4 - 9】二叉树的非递归后序遍历
void NRPostOrder(BiTree bt)
{
    BiTNode *stack[MAXNODE];
    int top;
    BiTNode *p;
    if (bt == NULL)
        return;
    top = -1;
    p = bt;                           // p指向根结点
    while (!(p == NULL && top == -1)) //指针p为空且栈也为空时结束
    {
        while (p != NULL)
        { //将当前指针p压栈，设栈空间足够大
            top++;
            stack[top] = p;
            p = p->lchild； //指针指向p的左孩子结点
        }
        if (top > -1)           //栈不空
            if (stack[top] > 0) //第一次在栈中
            {
                p = stack[top]->rchild; //转向右子树
                stack[top] = -stack[top];
                //相当于结点第一次出栈、第二次进栈
            }
            else
            {                    //第二次在栈中
                p = -stack[top]; //出栈，访问
                top--;
                Visit(p);
                p = NULL;
            }
    }
}
#pragma endregion
#pragma region 【算法4 - 10】层次遍历二叉树
void LevelOrder(BiTree bt)
{
    BiTNode *queue[MAXNODE];
    int front, rear;
    if (bt == NULL)
        return;
    front = -1;
    rear = 0;
    queue[rear] = bt;
    while (front != rear) //队列非空时
    {
        front++;             //出队列
        Visit(queue[front]); //访问队首结点的数据域
        if (queue[front]->lchild != NULL)
        //将队首结点的左孩子结点入队列
        {
            rear++;
            queue[rear] = queue[front]->lchild;
        }
        if (queue[front]->rchild != NULL)
        //将队首结点的右孩子结点入队列
        {
            rear++;
            queue[rear] = queue[front]->rchild;
        }
    }
}
#pragma endregion
#pragma region 【算法4 - 11】建立二叉树的二叉链表
void CreateBinTree(BiTree *T)
{ //以先序遍历序列构造二叉链表存储的二叉树
    char ch;
    scanf("%c", &ch);
    if (ch == '0')
        *T = NULL; //读入0时，将相应结点置空
    else
    {
        *T = (BinTNode *)malloc(sizeof(BinTNode)); //生成结点空间
        *T->data = ch;
        CreateBinTree(&((*T)->lchild)); //构造二叉树的左子树
        CreateBinTree(&((*T)->rchild)); //构造二叉树的右子树
    }
}
#pragma endregion
#pragma region 【算法4 - 12】在二叉树bt 中查找值为x 的数据元素
BiTree Search(BiTree bt, datatype x)
{
    BiTree p;
    if (bt)
    {
        if (bt->data == x)
            return bt; //查找成功返回
        if (bt->lchild)
            p = Search(bt->lchild, x);
        //若有左子树，在左子树中继续查找
        if (p)
            return p;
        if (bt->rchild)
            p = Search(bt->rchild, x);
        //若有右子树，在右子树中继续查找
        if (p)
            return p;
    }
    return NULL; //查找失败返回
}
#pragma endregion
#pragma region 【算法 4 - 13】统计二叉树bt 中叶子结点的个数
int CountLeaf2(BiTree bt)
{ // bt为根结点的指针，返回值为bt的叶子数
    if (bt == NULL)
        return (0);
    if (bt->lchild == NULL && bt->rchild == NULL)
        return (1); //若bt为叶子，返回1
    return (CountLeaf2(bt->lchild) + CountLeaf2(bt->rchild));
    //若bt为分支结点，叶子数目等于bt的左右子树中的叶子之和
}
#pragma endregion
#pragma region 【算法4 - 14】根据先序序列和中序序列恢复二叉树
void ReBiTree(char preod[], char inod[], BiTree root)
{
    if (n <= 0)
        root = NULL;
    else
        PreInOd(preod, 1, n, inod, 1, n, &root);
}
void PreInOd(char preod[], int i, int j, char inod[], int k, int h, BiTree *t)
{ // preod [i…j]为先序子序列，inod[k…h]为中子序序列，*t 指向子树的根
    *t = (BiTNode *)malloc(sizeof(BiTNode));
    (*t)->data = preod[i]; // 先序序列的第一个结点是子树的根
    m = k;
    while (inod[m] != preod[i])
        m++; //在中序序列中寻找根结点的位置
    if (m == k)
        (*t)->lchild = NULL;
    else
        PreInOd(preod, i + 1, i + m - k, inod, k, m - 1, &((*t)->lchild));
    //递归调用，生成左子树
    if (m == h)
        (*t)->rchild = NULL else PreInOd(preod, i + m - k + 1, j, inod, m + 1, h, &((*t)->rchild));
    //递归调用，生成右子树
}
#pragma endregion
#pragma region 【算法4 - 15】建立中序线索二叉树
BiThrNodeType *pre;
BiThrTree InOrderThr(BiThrTree T)
{ //中序遍历二叉树T，并将其中序线索化，pre为全局变量。
    BiThrTree head;
    head = (BiThrNodeType *)malloc(sizeof(BiThrNodeType)) ；
               //设申请头结点成功
               head->ltag = 0;
    head->rtag = 1;      //建立头结点
    head->rchild = head; //右指针回指
    if (!T)
        head->lchild = head;
    //若二叉树为空，则左指针回指
    else
    {
        head->lchild = T;
        pre = head;
        InThreading(T);
        //中序遍历进行中序线索化
        pre->rchild = head;
        pre->rtag = 1; //最后一个结点线索化
        head->rchild = pre;
    }
    return head;
}
void InTreading(BiThrTree p)
{ //通过中序遍历进行中序线索化
    if (p)
    {
        InThreading(p->lchild); //左子树线索化
        if (p->lchild == NULL)  //前驱线索
        {
            p->ltag = 1;
            p->lchild = pre;
        }
        if (pre->rchild == NULL) //后继线索
        {
            pre->rtag = 1;
            pre->rchild = p;
        }
        pre = p;
        InThreading(p->rchild); //右子树线索化
    }
}
#pragma endregion
#pragma region 【算法4 - 16】在中序线索二叉树上寻找结点p 的中序前驱结点
BiThrNodeType *InPreNode(BiThrTree p)
{ //在中序线索二叉树上寻找结点p的中序前驱结点
    BiThrNodeType *pre;
    pre = p->lchild;
    if (p->ltag != 1)
        while (pre->rtag == 0)
            pre = pre->rchild;
    return (pre);
}
#pragma endregion
#pragma region 【算法4 - 17】在中序线索二叉树上寻找结点p 的中序后继结点
BiThrNodeType *InPostNode(BiThrTree p)
{ //在中序线索二叉树上寻找结点p的中序后继结点
    BiThrNodeType *post;
    post = p->rchild;
    if (p->rtag != 1)
        while (post->ltag == 0)
            post = post->lchild;
    return (post);
}
#pragma endregion
#pragma region 【算法4 - 18】遍历中序线索二叉树
BiThrTree Search(BiThrTree head)
{ // head 为头结点
    BiThrNodeType *p;
    p = head->lchild; //指向根结点
    while (p->ltag == 0 && p != head)
        p = p->lchild;
    //找中序遍历的第一个结点
    while (p != head)
    {
        Visit(p);
        p = InPostNode(p);
    }
}
#pragma endregion
#pragma region 【算法4 - 19】线索二叉树的更新
void InsertThrRight(BiThrTree s, BiThrTree p)
{ //在中序线索二叉树中插入结点p使其成为结点s的右孩子
    BiThrTree w;
    p->rchild = s->rchild;
    p->rtag = s->rtag;
    p->lchild = s;
    p->ltag = 1; //将s变为p的中序前驱
    s->rchild = p;
    s->rtag = 0; // p成为s的右孩子
    if (p->rtag == 0)
    //当s原来右子树不空时，找到s的后继w，变w为p的后继，p为w的前驱
    {
        w = InPostNode(p);
        //在以p为根结点的子树上找中序遍历下的第一个结点
        w->lchild = p;
    }
}
#pragma endregion

main()
{
    BiTree bt;
    CreateBinTree(&bt);
}